package com.jack.leetcode.eachproblem_2020;

import com.google.common.collect.Lists;

import java.util.*;

/**
 * Created by zhang_j on 2020/11/5
 */
public class 单词接龙 {

    public static void main(String[] args) {
        List<String> a = Lists.newArrayList("hot","dot","dog","lot","log","cog");
        System.out.println(ladderLength("hit", "cog", a));
        a = Lists.newArrayList("hot","dot","dog","lot","log");
        System.out.println(ladderLength("hit", "cog", a));
    }

    static Map<String, Integer> wordId = new HashMap<>();
    static List<List<Integer>> edges = new ArrayList<>();
    static int nodeNum = 0;

    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        for (String s : wordList) {
            addEdge(s);
        }
        addEdge(beginWord);
        if(!wordList.contains(endWord)){
            return 0;
        }
        int[] dis = new int[nodeNum];
        Arrays.fill(dis, Integer.MAX_VALUE);
        int beginId = wordId.get(beginWord), endId = wordId.get(endWord);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(beginId);

        dis[beginId] = 0;
        while(!queue.isEmpty()){
            Integer poll = queue.poll();
            if(poll == endId){
                return dis[poll] / 2 + 1;
            }
            for(int i : edges.get(poll)){
                if(dis[i] == Integer.MAX_VALUE){
                    dis[i] = dis[poll] + 1;
                    queue.add(i);
                }
            }
        }
        return 0;
    }

    private static void addEdge(String word){
        addWord(word);
        char[] chars = word.toCharArray();
        for(int i = 0;i < chars.length;i++){
            char tmp = chars[i];
            chars[i] = '*';
            String newWord = String.valueOf(chars);
            addWord(newWord);
            int t1 = wordId.get(word);
            int t2 = wordId.get(newWord);
            edges.get(t1).add(t2);
            edges.get(t2).add(t1);
            chars[i] = tmp;
        }
    }

    private static void addWord(String word){
        if(!wordId.containsKey(word)){
            wordId.put(word, nodeNum++);
            edges.add(new ArrayList<>());
        }
    }
}
